package 代码随想录.链表;

import common.ListNode;

public class a142环形链表2 {
    static public class Solution {
        public ListNode detectCycle(ListNode head) {
            ListNode slow = head;
            ListNode fast = head;
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
                if (slow == fast) {
                    ListNode ptr = head;
                    while (ptr != fast) {
                        ptr = ptr.next;
                        fast = fast.next;
                    }
                    return ptr;
                }
            }
            return null;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        ListNode p3 = new ListNode(-4);
        ListNode p2 = new ListNode(0, p3);
        ListNode p1 = new ListNode(2, p2);
        ListNode head = new ListNode(3, p1);
        p3.next = p1;
        ListNode listNode = solution.detectCycle(head);
        System.out.println(listNode.val);
    }
}
